Human-based computation

Human-based computation is a computer science technique in which a computational process performs its function by outsourcing certain steps to humans. This approach uses differences in abilities and alternative costs between humans and computer agents to achieve symbiotic human-computer interaction.

In traditional computation, a human employs a computer to solve a problem; a human provides a formalized problem description to a computer, and receives a solution to interpret. Human-based computation frequently reverses the roles; the computer asks a person or a large group of people to solve a problem, then collects, interprets, and integrates their solutions.

Contents 1 Early work 2 Classes of human-based computation 3 Methods of human-based computation 4 Incentives to participation 5 Human-based computation as a form of social organization 6 Applications 6.1 Human-assisted search ranking 7 See also 8 References 9 Footnotes 10 External links

Early work

Human-based computation research has its origins in the early work on interactive evolutionary computation. The idea behind interactive evolutionary algorithms is due to Richard Dawkins. In the Biomorphs software accompanying his book The Blind Watchmaker (Dawkins, 1986) the preference of a human experimenter is used to guide the evolution of two-dimensional sets of line segments. In essence, this program asks a human to be the fitness function of an evolutionary algorithm, so that the algorithm can use human visual perception and aesthetic judgment to do something that a normal evolutionary algorithm cannot do. However, it is difficult to get enough evaluations from a single human if we want to evolve more complex shapes. Victor Johnston and Karl Sims extended this concept by harnessing power of many people for fitness evaluation (Caldwell and Johnston, 1991; Sims, 1991). As a result, their programs could evolve beautiful faces and pieces of art appealing to public. These programs effectively reversed the common interaction between computers and humans. In these programs, the computer is no longer an agent of its user, but instead, a coordinator aggregating efforts of many human evaluators. These and other similar research efforts became the topic of research in interactive evolutionary computation or aesthetic selection, however the scope of this research was limited to outsourcing evaluation and, as a result, it was not fully exploring the full potential of the outsourcing.

Human-based genetic algorithm (HBGA) encourages human participation in multiple different roles. Humans are not limited to the role of evaluator, but can choose to perform a more diverse set of functions. In particular, they can contribute their innovative solutions into the evolutionary process, make incremental changes to existing solutions, and perform intelligent recombination. In short, HBGA outsources to humans all operations of a typical genetic algorithm. As a result of this outsourcing, HBGA can process the representations for which there is no computational innovation operators available, for example, natural languages. Thus, HBGA obviated the need for a fixed representational scheme that was a limiting factor of both standard and interactive EC. These algorithms can be also be viewed as novel forms of social organization coordinated by a computer program (Kosorukoff and Goldberg, 2002).

Classes of human-based computation

Human-based computation methods combine computers and humans in different roles. Malone (2009) proposed a way to describe division of labor in computation, that groups human-based methods into three classes. The following table uses the evolutionary computation model to describe four classes of computation, three of which rely on humans in some role. For each class, a representative example is shown. The classification is in terms of the roles (innovation or selection) performed in each case by humans and computational processes. This table is a slice of three-dimensional table. The third dimension defines if the organizational function is performed by humans or a computer. Here it is assumed to be performed by a computer.

Division of labor in computation Selection agent Innovation agent Computer Human Computer Genetic Algorithm Interactive genetic algorithm Human Computerized Tests Human-based genetic algorithm

Classes of human-based computation from this table can be referred by two-letter abbreviations: HC, CH, HH. Here the first letter identifies the type of agents performing innovation, the second letter specifies the type of selection agents. In some implementations (wiki is the most common example), human-based selection functionality might be limited, it can be shown with small h.

Methods of human-based computation

• (HC) Darwin (Vyssotsky, Morris, McIlroy, 1961) and Core War (Jones, Dewdney 1984) These are games where several programs written by people compete in a tournament (computational simulation) in which fittest programs will survive. Authors of the programs copy, modify, and recombine successful strategies to improve their chances of winning.

• (CH) Interactive EC (Caldwell and Johnston, 1991; Sims, 1991) IEC enables the user to create an abstract drawing only by selecting his/her favorite images, so human only performs fitness computation and software performs innovative role. [Unemi 1998] Simulated breeding style introduces no explicit fitness, just selection, which is easier for humans.

• (HH₂) Wiki (Cunningham, 1995) enabled editing the web content by multiple users, i.e. supported two types of human-based innovation (contributing new page and its incremental edits). However, the selection mechanism was absent until 2002, when wiki has been augmented with a revision history allowing for reversing of unhelpful changes. This provided means for selection among several versions of the same page and turned wiki into a tool supporting collaborative content evolution (would be classified as human-based evolution strategy in EC terms).

• (HH₃) Human-based genetic algorithm (Kosorukoff, 1998) uses both human-based selection and three types of human-based innovation (contributing new content, mutation, and recombination). Thus, all operators of a typical genetic algorithm are outsourced to humans (hence the origin of human-based). This idea is extended to integrating crowds with genetic algorithm to study creativity in 2011 (Yu and Nickerson, 2011).

• (HH₁) Social search applications accept contributions from users and attempt to use human evaluation to select the fittest contributions that get to the top of the list. These use one type of human-based innovation. Early work was done in the context of HBGA. Digg and Reddit are recently popular examples.

• (HC) Computerized tests. A computer generates a problem and presents it to evaluate a user. For example CAPTCHA tells human users from computer programs by presenting a problem that is supposedly easy for a human and difficult for a computer. While CAPTCHAs are effective security measures for preventing automated abuse of online services, the human effort spent solving them is otherwise wasted. The reCAPTCHA system makes use of these human cycles to help digitize books by presenting words from scanned old books that optical character recognition cannot decipher. (von Ahn et al., 2008).

• (HC) Interactive online games: These are programs that extract knowledge from people in an entertaining way (Burgener, 1999; von Ahn 2003).

Incentives to participation

In different human-based computation projects people are motivated by one or more of the following.

• Receiving a fair share of the result
• Direct monetary compensation (e.g. in Amazon Mechanical Turk, Answerly Operator, ChaCha Search guide, Mahalo.com Answers members), HumanGrid
• Desire to diversify their activity (e.g. "people aren't asked in their daily lives to be creative" ^[1])
• Esthetic satisfaction
• Curiosity, desire to test if it works
• Volunteerism, desire to support a cause of the project
• Reciprocity, exchange, mutual help
• Desire to be entertained with the competitive or cooperative spirit of a game
• Desire to communicate and share knowledge
• Desire to share a user innovation to see if someone else can improve on it
• Desire to game the system and influence the final result
• Fun
• Increasing online reputation/recognition

Many projects had explored various combinations of these incentives. See more information about motivation of participants in these projects in Kosorukoff (2000) and von Hippel (2005).

Human-based computation as a form of social organization

Viewed as a form of social organization, human-based computation often surprisingly turns out to be more robust and productive than traditional organizations (Kosorukoff and Goldberg, 2002). The latter depend on obligations to maintain their more or less fixed structure, be functional and stable. Each of them is similar to a carefully designed mechanism with humans as its parts. However, this limits the freedom of their human employees and subjects them to various kinds of stresses. Most people, unlike mechanical parts, find it difficult to adapt to some fixed roles that best fit the organization. Evolutionary human-computation projects offer a natural solution to this problem. They adapt organizational structure to human spontaneity, accommodate human mistakes and creativity, and utilize both in a constructive way. This leaves their participants free from obligations without endangering the functionality of the whole, making people happier. There are still some challenging research problems that need to be solved before we can realize the full potential of this idea.

The algorithmic outsourcing techniques used in human-based computation are much more scalable than the manual or automated techniques used to manage outsourcing traditionally. It is this scalability that allows to easily distribute the effort among thousands of participants. It was suggested recently that this mass outsourcing is sufficiently different from traditional small-scale outsourcing to merit a new name crowdsourcing (Howe, 2006).

Applications

Human-assisted search ranking

An approach to improving internet search involves combining automated ranking with human editorial input.^[2]

See also

• Citizen science
• Collaborative intelligence
• Collaborative Innovation Networks
• Collaborative human interpreter
• Crowdsourcing
• Game with a purpose (or GWAP)
• Galaxy Zoo
• Human computer
• Human Computer Information Retrieval
• Simulated reality
• Social software
• Social computing
• Social organization
• Symbiotic intelligence
• Zooniverse (citizen science project)

References

Footnotes

External links

• Human Computation, a Google Tech Talk by Luis von Ahn
• Utyp, Open Source Human Computation based Search Engine for images and pictures utilizing a Flash game